#include "leetcode_util.h"

/* given two strings, find the longest common subsequence
 * abcdefg bcjkfi
 * it should be [b c f]
 * OUTPUT: 3
 */

int solution1( vector<char>& A, vector<char>& B )
{
    vector<int> results;
    int         l_a = A.size();
    int         l_b = B.size();
    for ( int i = 0; i < l_a; ++i ) {
        // for each item in A
        auto find_in_b = find( B.begin(), B.end(), A[i] );
        // find a, no
        if ( find_in_b < B.end() ) {
            // find b, yes
            int res = 1;
            for ( int j = i + 1; j < l_a; ++j ) {
                auto found = find( find_in_b + 1, B.end(), A[j] );
                // find d, no
                if ( found < B.end() ) {
                    // find c, yes
                    find_in_b = found;
                    ++res;
                }
            }
            results.push_back( res );
        }
    }
    int res = *max_element( results.begin(), results.end() );
    return res;
}

// abcdefg bcjkfi -> bcf
// from the tail, recursively find the sommon subsequences from the substrings
int helper2( vector<char>& A, int idx1, vector<char>& B, int idx2, int count )
{
    if ( idx1 < 0 || idx2 < 0 )
        return count;
    if ( A[idx1] == B[idx2] ) {
        // assume abcdefg|x & bcjkfi|x -> bcf|x
        // x should be in the common subsequence
        count++;
        // then consider the left without x
        return helper2( A, idx1 - 1, B, idx2 - 1, count );
    }
    else {
        // (abcdef|g & bcjkfi) or (abcdefg &bcjkf|i)
        return max( helper2( A, idx1 - 1, B, idx2, count ), helper2( A, idx1, B, idx2 - 1, count ) );
    }
}
int solution2( vector<char>& A, vector<char>& B )
{
    return helper2( A, A.size() - 1, B, B.size() - 1, 0 );
}

// dp: from the bottom of recursive calls
int solution3( vector<char>& A, vector<char>& B )
{
    if ( A.empty() || B.empty() )
        return 0;
    int m = A.size();
    int n = B.size();
    int dp[m + 1][n + 1];
    memset( dp, 0, sizeof( dp ) );
    for ( int i = 1; i < m + 1; ++i ) {
        for ( int j = 1; j < n + 1; ++j ) {
            if ( A[i - 1] == B[j - 1] ) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max( dp[i - 1][j], dp[i][j - 1] );
            }
        }
    }
    return dp[m][n];
}
/*
def LongestCommonSubsequence(A, B):
    dp = [ [ 0 for n in range(len(B)+1) ] for m in range(len(A)+1) ]
    for i in range(len(A)):
        for j in range(len(B)):
            if A[i] == B[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return dp[len(A)][len(B)]
*/

#ifdef SOLO_SOLUTION
void showVector( vector<int>& A )
{
    vector<int>::iterator itr = A.begin();
    for ( ; itr != A.end(); ) {
        printf( "%d", *itr );
        if ( ++itr != A.end() ) {
            printf( " " );
        }
        else {
            printf( "\n" );
        }
    }
}

void testVector( int argc, char* argv[] )
{
    string s;
    for ( int i = 1; i < argc; i++ ) {
        s             = string( argv[i] );
        vector<int> v = stringToVector( s );
        // test function

        // cout << numberOfArithmeticSlices(v) << endl;
    }
}

int main( int argc, char* argv[] )
{
    // string s = "abcfbc abfcab";
    // string s = "abfcab abcfbc";
    // string s = "programming contest";
    string s = "abcdefg cdebcjkfi";
    // string s = "abcd mnp";
    stringstream   ss( s );
    vector<string> s0;
    string         token;
    while ( getline( ss, token, ' ' ) ) {
        s0.push_back( token );
    }
    vector<char> a( s0[0].begin(), s0[0].end() );
    vector<char> b( s0[1].begin(), s0[1].end() );

    int     result;
    int     N       = 10000;
    clock_t c_start = clock();
    for ( int i = 0; i < N; ++i ) {
        result = solution1( a, b );
    }
    cout << "solution1: " << result << " - " << float( clock() - c_start ) / CLOCKS_PER_SEC << endl;
    c_start = clock();
    for ( int i = 0; i < N; ++i ) {
        result = solution2( a, b );
    }
    cout << "solution2: " << result << " - " << float( clock() - c_start ) / CLOCKS_PER_SEC << endl;
    c_start = clock();
    for ( int i = 0; i < N; ++i ) {
        result = solution3( a, b );
    }
    cout << "solution3: " << result << " - " << float( clock() - c_start ) / CLOCKS_PER_SEC << endl;
}
#endif